注意本篇题解的 是题目中的 。
这道题 肯定不为 , 后面的值为 ,只需考虑前一个和式。
自然数幂和是一个 次多项式,可以用伯努利数算出系数,不妨记为 。
由伯努利公式得:
后面的和式是一个积性函数,考虑质数取值
由 的性质,只有 或 时不为 ,所以上式等于 。
所以我们能 计算出这个式子。
那么预处理出伯努利数和 ,原题便能 解决了。
#include <cstdio>
const int MAXK = 105 , Mod = 1e9 + 7;
int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { return 1ll * x * y % Mod; }
int Quick_pow( int x , int po ) { int Ans = 1; for( ; po ; po >>= 1 , x = Mul( x , x ) ) if( po & 1 ) Ans = Mul( Ans , x ); return Ans; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int Div( int x , int y ) { return Mul( x , Inv( y ) ); }
int fac[ MAXK + 10 ] , ivf[ MAXK + 10 ];
void Init( ) {
fac[ 0 ] = 1;
for( int i = 1 ; i <= MAXK + 5 ; i ++ ) fac[ i ] = Mul( fac[ i - 1 ] , i );
ivf[ MAXK + 5 ] = Inv( fac[ MAXK + 5 ] );
for( int i = MAXK + 5 ; i >= 1 ; i -- ) ivf[ i - 1 ] = Mul( ivf[ i ] , i );
}
int C( int n , int m ) { return Mul( fac[ n ] , Mul( ivf[ m ] , ivf[ n - m ] ) ); }
int w , k , p[ 1005 ] , a[ 1005 ];
int B[ MAXK + 5 ] , f[ MAXK + 5 ];
void Init_Bernoulli( ) {
B[ 0 ] = 1;
for( int i = 1 ; i <= MAXK ; i ++ ) {
int Sum = 0;
for( int j = 0 ; j < i ; j ++ ) Sum = Add( Sum , Mul( C( i + 1 , j ) , B[ j ] ) );
B[ i ] = Sub( 0 , Mul( Sum , Inv( C( i + 1 , i ) ) ) );
}
for( int i = 0 ; i <= k ; i ++ ) f[ k + 1 - i ] = Div( Mul( C( k + 1 , i ) , B[ i ] ) , k + 1 );
}
int Sum( int pw ) {
if( pw < 0 ) pw += Mod - 1;
int Ans = 1;
for( int i = 1 ; i <= w ; i ++ ) Ans = Mul( Ans , Sub( 1 , Quick_pow( p[ i ] , pw ) ) );
return Ans;
}
int main( ) {
scanf("%d %d",&k,&w);
Init(); Init_Bernoulli();
for( int i = 1 ; i <= w ; i ++ ) scanf("%d %d",&p[ i ],&a[ i ]);
int Ans = 0 , n = 1;
for( int i = 1 ; i <= w ; i ++ ) n = Mul( n , Quick_pow( p[ i ] , a[ i ] ) );
for( int i = 1 , nk = 1 ; i <= k + 1 ; i ++ ) {
nk = Mul( nk , n );
Ans = Add( Ans , Mul( Mul( f[ i ] , nk ) , Sum( k - i ) ) );
}
printf("%d\n", Ans );
return 0;
}